package edu.columbia.aicheckers.agent;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

import edu.columbia.aicheckers.model.Checker;
import edu.columbia.aicheckers.model.Color;
import edu.columbia.aicheckers.model.IBoardState;
import edu.columbia.aicheckers.model.Move;

/**
 * A class containing various helper methods for the intelligent agents
 * @author C.M.R.
 */
public class AgentHelper {
	
	public static double DISCOUNT_FACTOR = 0.9;
	
	public static int DEEP_SEARCH = 3;
	public static int SHALLOW_SEARCH = 2;
	
	private Queue<Move> pastMoves = new LinkedList<Move>();

	private BitSet attributes;
	
	public static final int KING_PREFERENCE = 0;
	public static final int AGGRESSIVE_START_GAME = 1;
	public static final int AGGRESSIVE_MID_GAME = 2;
	public static final int AGGRESSIVE_END_GAME = 3;
	public static final int OPTIMAL_OPPONENT = 4;
	public static final int BOARD_SIDE_PREFERENCE = 5;
	public static final int AVOID_STALEMATE = 6;
	public static final int DOUBLE_SKIP_PREFERENCE = 7;
	public static final int SKIP_KINGS_PREFERENCE = 8;
	public static final int AVOID_BEING_SKIPPED = 9;
	public static final int USE_DISCOUNT_FACTOR = 10;
	public static final int AGGRESSIVE_OPPONENT = 11;
	public static final int DEEP_SEARCH_ATTRIBUTE = 12;

	public static final int NUM_ATTRIBUTES = 13;
	
	public AgentHelper(BitSet bitSet)
	{
		this.attributes = bitSet;
	}
	
	
	/**
	 * A method that chooses the best move based on those that are available
	 * and based upon the particular agent used
	 * @param state
	 * @param myColor
	 * @param checkStalemate
	 * @return
	 */
	public Move moveSelection(IBoardState state, Color myColor, boolean checkStalemate)
	{
		Set<Move> moves = state.getAvailableMoves(myColor);
		double maxUtility = Double.MIN_VALUE;
		Move bestMove = null;
		Move nextBestMove = null;
		if(moves.isEmpty())
		{
			return null;
		}
		for(Move m : moves)
		{
			IBoardState next = state.simulateMove(m);
			BoardStateWrapper w = new BoardStateWrapper(next);
			w.m = m;
			if(has(DEEP_SEARCH_ATTRIBUTE))
				depthFirstSearch(w, myColor, DEEP_SEARCH, 0);
			else
				depthFirstSearch(w, myColor, SHALLOW_SEARCH, 0);
			if(w.utility > maxUtility || maxUtility == Double.MIN_VALUE)
			{
				maxUtility = w.utility;
				nextBestMove = bestMove;
				bestMove = m;
			}
		}
		if(has(AVOID_STALEMATE) && checkStalemate)
		{
			if(bestMove!= null && isRedundantMove(bestMove) && nextBestMove != null)
			{
				// Choose next best move
				bestMove = nextBestMove;
				
			}
		}
		pastMoves.add(bestMove);
		if(pastMoves.size() > 4)
		{
			pastMoves.remove();
		}
		
		return bestMove;
		
	}
	
	/**
	 * Checks for redundant moves
	 * @param moveToTake
	 * @return
	 */
	public boolean isRedundantMove(Move moveToTake) {
		for(Move m : pastMoves )
		{
			if(m != null && (moveToTake.getCheckerPiece() == m.getCheckerPiece() 
					&& moveToTake.getDestination() == m.getDestination()))
			{
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Determine the reward of the current board state based on a sequence of moves
	 * @param state
	 * @param myColor
	 * @param depth
	 * @return
	 */
	public int getReward(IBoardState state, Color myColor, int depth)
	{
		boolean useDiscountFactor = has(USE_DISCOUNT_FACTOR);
		boolean aggressive = isStartGame(state) ? has(AGGRESSIVE_START_GAME) : (isMidGame(state) ? has(AGGRESSIVE_MID_GAME) : has(AGGRESSIVE_END_GAME));
		int utility = utilityFunction(state, myColor, aggressive);
		utility *= useDiscountFactor ? Math.pow(DISCOUNT_FACTOR,depth) : 1;
		return utility;
	}
	
	
	/**
	 * A depth first search to check a tree of possible moves
	 * @param root
	 * @param myColor
	 * @param maxDepth
	 * @param depth
	 */
	public void depthFirstSearch(BoardStateWrapper root, Color myColor,
			int maxDepth, int depth) {
		if(depth == maxDepth)
		{
			root.utility = getReward(root.s,myColor,depth); 
		}
		else
		{
			IBoardState state = root.s;
			boolean myMove = (state.getCurrentPly() == myColor);
			Set<Move> moves = state.getAvailableMoves(state.getCurrentPly());
			depth++;
			HashMap<Move,Double> opponentProbability = null;
			if(!myMove)
			{
				opponentProbability = getOpponentMoveProbability(state, myColor);
			}
			for (Move m : moves) {
				
				IBoardState next = state.simulateMove(m);
				
				BoardStateWrapper child = new BoardStateWrapper(next);
				child.m = m;
				root.children.add(child);
				depthFirstSearch(child, myColor,maxDepth,depth);
				if(myMove)
				{
					root.utility += child.utility;
					if(m.hasSkip() && root.m.hasSkip() && root.m.getCheckerPiece().getColor() == myColor)
					{
						root.utility += has(DOUBLE_SKIP_PREFERENCE) ? 2 : 0;
					}
				}
				else
				{
//					root.utility += child.utility * opponentProbability.get(m);
					root.utility += child.utility;
				}
				
			}
		}
		
		
	}
	
	/**
	 * Checks opponent probability of making a move
	 * @param state
	 * @param myColor
	 * @return
	 */
	public HashMap<Move,Double> getOpponentMoveProbability(IBoardState state, Color myColor)
	{
		HashMap<Move,Double> moveToProbability  = new HashMap<Move, Double>();
		boolean isOptimalOpponent = has(OPTIMAL_OPPONENT);
		Set<Move> opponentMoves = state.getAvailableMoves(Color.getOponnentColor(myColor));
		
		
		int totalReward = 0;
		int maxReward = Integer.MIN_VALUE;
		Move optimalMove = null;
		for(Move m : opponentMoves)
		{
			IBoardState next = state.simulateMove(m);
			boolean aggressiveOpponent = has(AGGRESSIVE_OPPONENT);
			int reward = utilityFunction(next, Color.getOponnentColor(myColor) , aggressiveOpponent);
			if(reward > maxReward)
			{
				maxReward = reward;
				optimalMove = m;
			}
			moveToProbability.put(m,(double)reward);
			totalReward += reward;
		}
		
		for(Move m : opponentMoves)
		{
			if(isOptimalOpponent)
			{
				if(m == optimalMove)
				{
					moveToProbability.put(m,1.0);
				}
				else {
					moveToProbability.put(m,0.0);
				}
			} else
			{
				double reward = moveToProbability.get(m);
				moveToProbability.put(m,reward/totalReward);
			}

		}
		return moveToProbability;
	}
	
	/**
	 * Utility function is always positive
	 * @param state
	 * @param myColor
	 * @param aggressive
	 * @return
	 */
	public int utilityFunction(IBoardState state, Color myColor, boolean aggressive)
	{
		int kingPreference = has(KING_PREFERENCE) ? 4 : 1;
		int boardSidePreference = has(BOARD_SIDE_PREFERENCE) ? 2 : 0;
		int avoidBeingSkipped = has(AVOID_BEING_SKIPPED) ? 4 : 1;
		int skipKingPreference = has(SKIP_KINGS_PREFERENCE) ? 2 : 0;
		
		// Calculate total board balance
		int boardBalance = 16;
		for(int i = 1; i <= 32; i++)
		{
			int value = 0;
			Checker c = state.getChecker(i);
			
			if(c == null)
			{
				value = 0;
			}
			else
			{
				if(c.isKing())
				{
					value = kingPreference;
				}
				else
				{
					value = 1;
				}
				if(isSide(c.getLocation()))
				{
					value += boardSidePreference;
				}
				
				if(myColor != c.getColor())
					value = -value;
			}
			boardBalance += value;
			
		}
		// Get the available moves for this state
		
		Set<Move> moves = state.getAvailableMoves(state.getCurrentPly());
		
		int skippingMoves = 0;
		if(state.getCurrentPly() == myColor)
		{
			for(Move m : moves)
			{
				if(aggressive)
					skippingMoves += m.hasSkip() ? 10 : 0;
				else
					skippingMoves += m.hasSkip() ? 5 : 0;
				
				if(m.hasSkip() && state.getChecker(m.getSkippedLocation()).isKing())
				{
					skippingMoves += skipKingPreference;
				}
			}
		}
		else
		{
			for(Move m : moves)
			{
				skippingMoves -= m.hasSkip() ? avoidBeingSkipped : 0;
			}
		}
		
		boardBalance += skippingMoves;
		
		return boardBalance > 0 ? boardBalance : 1;
		
	}

	/**
	 * Checks to start the game
	 * @param s
	 * @return
	 */
	private static boolean isStartGame(IBoardState s)
	{
		int total = 0;
		for(int i = 1; i <= 32; i++)
		{
			Checker c = s.getChecker(i);
			if(c != null)
			{
				total++;
			}
		}
		return total >= 16;
	}
	
	private static boolean isMidGame(IBoardState s)
	{
		int total = 0;
		for(int i = 1; i <= 32; i++)
		{
			Checker c = s.getChecker(i);
			if(c != null)
			{
				total++;
			}
		}
		return total < 16 && total >= 8;
	}
	
	
	private static boolean isEndGame(IBoardState s)
	{
		int total = 0;
		for(int i = 1; i <= 32; i++)
		{
			Checker c = s.getChecker(i);
			if(c != null)
			{
				total++;
			}
		}
		return total < 8;
	}
	
	private static boolean isSide(int location) {
		if(		location == 1 || 
				location == 2 || 
				location == 3 || 
				location == 4 || 
				location == 5 || 
				location == 13 || 
				location == 21 || 
				location == 29 || 
				location == 30|| 
				location == 31 || 
				location == 32 || 
				location == 12 || 
				location == 20 || 
				location == 28)
		{
			return true;
		}
		return false;
	}

	private boolean has(int preference) {
		// TODO Auto-generated method stub
		return attributes.get(preference);
	}
	
	private class BoardStateWrapper
	{
		public double utility = 0.0;

		IBoardState s;
		Move m;
		
		ArrayList<BoardStateWrapper> children = new ArrayList<BoardStateWrapper>();
		
		public BoardStateWrapper(IBoardState s)
		{
			this.s = s;
		}
		
		
	}
}
